package com.sicheng.lc.周赛.分类.并差集;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/14 22:23
 */
public class 岛屿的最大面积 {
    //    https://leetcode.cn/problems/max-area-of-island/
    int[] p, size;
    int m, n, max;

    int find(int x) {
        if (x == p[x])
            return x;
        return p[x] = find(p[x]);
    }

    int get(int i, int j) {
        return i * n + j;
    }

    void union(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
            size[pb] += size[pa];
            max = Math.max(size[pb], max);
        }
    }

    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        init(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    if (i - 1 >= 0 && grid[i - 1][j] == 1) {
                        union(get(i, j), get(i - 1, j));
                    }
                    if (j - 1 >= 0 && grid[i][j - 1] == 1) {
                        union(get(i, j), get(i, j - 1));
                    }
                    if (i + 1 < m && grid[i + 1][j] == 1) {
                        union(get(i, j), get(i + 1, j));
                    }
                    if (j + 1 < n && grid[i][j + 1] == 1) {
                        union(get(i, j), get(i, j + 1));
                    }
                }
            }
        }

        return max;

    }

    private void init(int[][] grid) {
        p = new int[m * n];
        size = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    p[get(i, j)] = get(i, j);
                    size[get(i, j)] = 1;
                    max = 1;
                }
            }
        }
    }


}
